#include <opencv2/opencv.hpp>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;
using namespace cv;
int width = 640, height = 480;

inline float computeDistance(cv::Point2f& point)
{
    return point.x*point.x + (height-point.y)*(height-point.y);
}

inline float cross(cv::Point2f vec0, cv::Point2f vec1)
{
    return vec0.x*(height-vec1.y) - vec1.x*(height-vec0.y);
}

inline float cross0(cv::Point2f vec0, cv::Point2f vec1)
{
    return vec0.x*(-vec1.y) - vec1.x*(-vec0.y);
}

int sortPoint(vector<cv::Point2f> &data)
{
    vector<cv::Point2f>::iterator begin_ = data.begin(), end_ = data.end();
    begin_++;
    sort(begin_,end_,[&data](cv::Point2f& p0,cv::Point2f& p1){
        float result_ = cross0(p0-data[0], p1-data[0]);
        if (result_ > 0.f)  return true;
        return false;
    });
}

int findMaxIncludeArea(vector<cv::Point2f> &data,vector<int>& outline)
{
    cv::Mat image(height,width,CV_8UC3,cv::Scalar(255,255,255));
    int left_down_index = 0;
    for (int i = 0; i < data.size(); ++i) {
        if( (data[i].y > data[left_down_index].y) ||
                ((data[i].y==data[left_down_index].y) && (data[i].x < data[left_down_index].x))
          )
            left_down_index = i;
    }
    std::swap(data[0],data[left_down_index]);
    sortPoint(data);

    for (int i = 0; i < data.size(); ++i) {
        cv::circle(image,data[i],1,Scalar(0,0,255));
        cv::putText(image,to_string(i),data[i],1,1,Scalar(0,0,0));
    }
#ifdef DEBUG_DATA
    cv::Mat sortMat = image.clone();
    for (int i = 1; i < data.size(); ++i) {
        cv::line(sortMat,data[i],data[0],Scalar(0,0,255));
    }
    imshow("sort",sortMat);
    cv::waitKey();
#endif

    outline.clear();
    outline.push_back(0);
    outline.push_back(1);
    outline.push_back(2);

    for (int i = 3; i < data.size(); ++i) {
        float score = cross0((data[outline[outline.size()-1]]-data[outline[outline.size()-2]]),(data[i]-data[outline[outline.size()-2]]));
        while (score<0)
        {
            int popEle = outline.back();
            outline.pop_back();
            cout << "pop back: " << popEle << ", with score = " << score << endl;
            score = cross0((data[outline[outline.size()-1]]-data[outline[outline.size()-2]]),(data[i]-data[outline[outline.size()-2]]));
        }
        outline.push_back(i);
#ifdef DEBUG_DATA
        cv::Mat showData = image.clone();
        cout << "push back: " << i << ", with score = " << score  << endl;
        cv::line(showData,data[outline[outline.size()-1]],data[outline[outline.size()-2]],Scalar(0,0,255));
        cv::line(showData,data[outline[outline.size()-2]],data[outline[outline.size()-3]],Scalar(0,0,255));
        cv::imshow("showData",showData);
        cv::waitKey();
#endif
    }
    for (int i = 3; i < outline.size(); ++i) {
        cv::line(image,data[outline[i-1]],data[outline[i]],Scalar(0,0,255));
    }
    for (int i = 0; i < 2; ++i) {
        cv::line(image,data[outline[i]],data[outline[i+1]],Scalar(125,0,0));
    }
    cv::line(image,data[outline.back()],data[outline[0]],Scalar(205,120,0));
    cv::imshow("showData",image);
    cv::waitKey();
    return 0;
}

int main(int argc, char *argv[])
{
    if(argc==3) {
        width = atoi(argv[1]);
        height = atoi(argv[2]);
    }
    cv::Mat image(height,width,CV_8UC3,cv::Scalar(255,255,255));

    vector<cv::Point2f> data;
    data.reserve(50);

    srand(int(time(0)));
    for (int i = 0; i < 50; ++i) {
        float x_=rand()%(width*100)*0.01,y_=rand()%(height*100)*0.01;

        cv::Point2f point(x_,y_);
        data.push_back(point);
        cv::circle(image,point,1,Scalar(0,0,255));
    }
    vector<int> outline;
    findMaxIncludeArea(data,outline);

    return 0;
}
